/**
 * 给定012二维数组，找到如下最长的模式
 * 1. 从1开始，以后按2、0、2、0重复
 * 2. 沿对角线的4个方向之一
 * 3. 允许顺时针转向一次（显然仍然是对角线四方向之一），也可以不转
 * 
 * 令Dijo记录位置(i,j)方向o的最长长度
 * 使用记忆化完成
 * 
 * 对每一个为1的位置，依次检测4个方向:
 *    令t是某个方向的最大值
 *    再for一遍t检测第二个方向
 * 
 * 时间最长是O(N^3)，但应该达不到？
 */

using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

const vector<pii> Z {
    pii{-1, -1},
    pii{-1, +1},
    pii{+1, +1},
    pii{+1, -1}
};

int N, M;
vector<vvi> D;
vector<vi> * pVec;

int dp(int r, int c, int o){
    if(-1 != D[r][c][o]) return D[r][c][o];

    int nr = r + Z[o].first;
    int nc = c + Z[o].second;
    if(0 <= nr and nr < N and 0 <= nc and nc < M and ((*pVec)[nr][nc] ^ (*pVec)[r][c]) == 2){
        return D[r][c][o] = 1 + dp(nr, nc, o);
    }
    return D[r][c][o] = 1;
}

class Solution {
public:
    int lenOfVDiagonal(vector<vector<int>>& grid) {
        N = grid.size();
        M = grid[0].size();
        D.assign(N, vvi(M, vi(4, -1)));
        pVec = &grid;

        int ans = -1;
        for(int i=0;i<N;++i)for(int j=0;j<M;++j){
            if(grid[i][j] != 1) continue;
            if(-1 == ans) ans = 0;
            for(int nr,nc,o=0;o<4;++o){
                nr = Z[o].first + i;
                nc = Z[o].second + j;
                if(0 <= nr and nr < N and 0 <= nc and nc < M and grid[nr][nc] == 2){
                    int c = (o + 1) % 4;
                    auto tmp = dp(nr, nc, o);
                    for(int k=0;k<tmp;++k){
                        auto t2 = dp(nr, nc, c);
                        ans = max(ans, k + t2);
                        nr += Z[o].first;
                        nc += Z[o].second;
                    }
                }
            }
        }
        return ans + 1;
    }
};